|
In graph theory, a bipolar orientation or ''st''-orientation of an undirected graph is an assignment of a direction to each edge (an orientation) that causes the graph to become a directed acyclic graph with a single source ''s'' and a single sink ''t'', and an ''st''-numbering of the graph is a topological ordering of the resulting directed acyclic graph.〔〔 ==Definitions and existence== Let ''G'' = (''V'',''E'') be an undirected graph with ''n'' = |''V''| vertices. An orientation of ''G'' is an assignment of a direction to each edge of ''G'', making it into a directed graph. It is an acyclic orientation if the resulting directed graph has no directed cycles. Every acyclically oriented graph has at least one ''source'' (a vertex with no incoming edges) and at least one ''sink'' (a vertex with no outgoing edges); it is a bipolar orientation if it has exactly one source and exactly one sink. In some situations, ''G'' may be given together with two designated vertices ''s'' and ''t''; in this case, a bipolar orientation for ''s'' and ''t'' must have ''s'' as its unique source and ''t'' as its unique sink.〔〔 An ''st''-numbering of ''G'' (again, with two designated vertices ''s'' and ''t'') is an assignment of the integers from 1 to ''n'' to the vertices of ''G'', such that *each vertex is assigned a distinct number, *''s'' is assigned the number 1, *''t'' is assigned the number ''n'', and *if a vertex ''v'' is assigned the number ''i'' with 1 < ''i'' < ''n'', then at least one neighbor of ''v'' is assigned a smaller number than ''i'' and at least one neighbor of ''v'' is assigned a larger number than ''i''.〔〔〔 A graph has a bipolar orientation if and only if it has an ''st''-numbering. For, if it has a bipolar orientation, then an ''st''-numbering may be constructed by finding a topological ordering of the directed acyclic graph given by the orientation, and numbering each vertex by its position in the ordering. In the other direction, every ''st''-numbering gives rise to a topological ordering, in which each edge of ''G'' is oriented from its lower-numbered endpoint to its higher-numbered endpoint.〔〔 In a graph containing edge ''st'', an orientation is bipolar if and only if it is acyclic and the orientation formed by reversing edge ''st'' is totally cyclic.〔 A connected graph ''G'', with designated vertices ''s'' and ''t'', has a bipolar orientation and an ''st''-numbering if and only if the graph formed from ''G'' by adding an edge from ''s'' to ''t'' is 2-vertex-connected.〔 In one direction, if this graph is 2-vertex-connected, then a bipolar orientation may be obtained by consistently orienting each ear in an ear decomposition of the graph.〔 In the other direction, if the graph is not 2-vertex-connected, then it has an articulation vertex ''v'' separating some biconnected component of ''G'' from ''s'' and ''t''. If this component contains a vertex with a lower number than ''v'', then the lowest-numbered vertex in the component cannot have a lower-numbered neighbor, and symmetrically if it contains a vertex with a higher number than ''v'' then the highest-numbered vertex in the component cannot have a higher-numbered neighbor. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「bipolar orientation」の詳細全文を読む スポンサード リンク
|